package com.base.dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 * <p>
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 * <p>
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 * <p>
 * 注意：不允许旋转信封。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 * 示例 2：
 * <p>
 * 输入：envelopes = [[1,1],[1,1],[1,1]]
 * 输出：1
 */
public class MaxEnvelopes {

    public static void main(String[] args) {
        MaxEnvelopes maxEnvelopes = new MaxEnvelopes();
        System.out.println(maxEnvelopes.maxEnvelopes(new int[][]{{5, 4}, {6, 4}, {6, 7}, {2, 3}}));
    }

    /**
     * 超时了，面对大数据量时
     *
     * @param envelopes
     * @return
     */
    public int maxEnvelopes(int[][] envelopes) {
        // 按宽度升序排序，如果宽度相同，则按高度降序排序
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // 高度降序
            }
            return a[0] - b[0]; // 宽度升序
        });

        // 提取所有信封的高度
        int[] heights = new int[envelopes.length];
        for (int i = 0; i < envelopes.length; i++) {
            heights[i] = envelopes[i][1];
        }
        // 使用二分查找寻找最长递增子序列的长度
        return lengthOfLIS(heights);
    }

    /**
     * 二分查找法
     *
     * @param heights 输入的数组，我们希望找到这个数组中的最长递增子序列
     * @return 结果
     */
    private int lengthOfLIS(int[] heights) {
        //记录当前找到的递增子序列的最大长度
        int piles = 0;
        //一个辅助数组，用来存储当前找到的递增子序列。top[i] 表示长度为 i+1 的递增子序列的最后一个元素。
        int[] top = new int[heights.length];
        //每个高度都查找一遍吗？还是啥意思？每个元素在top数组里面比较一次吗
        for (int i : heights) {
            int left = 0;
            int right = piles;
            //
            while (left < right) {
                int mid = (left + right) / 2;
                if (top[mid] >= i) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            //进过上面的while循环，已经找到了当前元素i应该在top[]中的位置了
            if (left == piles) {
                //这意味着 num 大于 top 数组中所有已存在的元素，
                //因此我们可以扩展递增子序列的长度，将 num 放在 top[piles] 的位置，
                // 并将 piles 加 1。
                piles++;

            }
            //当前i所在的位置是left
            // 如果 left 小于 piles，则 num 可以替换 top[left]，
            // 因为 num 比 top[left] 小，
            // 这样可以为后续的元素提供更大的递增子序列的可能性。
            top[left] = i;
        }
        return piles;

    }

}
